package com.platform.modules.alg.alglib.poj3237;

public class Poj3237A {
    private int inf = 0x3f3f3f3f;
    private int N = 40005;
    int n, top;
    int c[][] = new int[N][2];
    int fa[] = new int[N];
    int v[] = new int[N];
    int mx[] = new int[N];
    int mn[] = new int[N];
    int st[] = new int[N];
    int rev[] = new int[N];
    int reg[] = new int[N];
    public String output = "";

    public String cal(String input) {
        int x, y, w;
        String opt;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        for (int i = 0; i < mx.length; i++) {
            mx[i] = -inf;
            mn[i] = inf;
        }
        for (int i = 1; i < n; i++) {
            String[] info = line[i].split(" ");
            x = Integer.parseInt(info[0]);
            y = Integer.parseInt(info[1]);
            w = Integer.parseInt(info[2]);
            v[i] = -inf;
            v[n + i] = w;
            link(x, n + i);
            link(n + i, y);
        }
        v[n] = -inf;
        int count = 0;
        while (true) {
            String[] query = line[n + count++].split(" ");
            opt = query[0];
            if (opt.charAt(0) == 'D') break;
            x = Integer.parseInt(query[1]);
            y = Integer.parseInt(query[2]);

            if (opt.charAt(0) == 'C') change(n + x, y);
            else if (opt.charAt(0) == 'Q') query(x, y);
            else if (opt.charAt(0) == 'N') neg(x, y);
        }

        return output;
    }

    void update(int x) {
        int l = c[x][0], r = c[x][1];
        mx[x] = Math.max(mx[l], mx[r]);
        mn[x] = Math.min(mn[l], mn[r]);
        if (v[x] != -inf && v[x] != inf) {
            mx[x] = Math.max(mx[x], v[x]);
            mn[x] = Math.min(mn[x], v[x]);
        }
    }

    // 先修改 + 打懒标
    void phr(int x) {
        reg[x] ^= 1;
        v[x] = -v[x];
        mx[x] = -mx[x];
        mn[x] = -mn[x];
        int temp = mx[x];
        mx[x] = mn[x];
        mn[x] = temp;
    }

    void pushdown(int x) {
        int l = c[x][0], r = c[x][1];
        if (rev[x] != 0) {
            rev[l] ^= 1;
            rev[r] ^= 1;
            rev[x] ^= 1;
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
        if (reg[x] != 0) {
            if (l > 0) phr(l);
            if (r > 0) phr(r);
            reg[x] ^= 1;
        }
    }

    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y], l, r;
        if (c[y][0] == x) l = 0;
        else l = 1;
        r = l ^ 1;
        if (!isroot(y)) {
            if (c[z][0] == y) c[z][0] = x;
            else c[z][1] = x;
        }
        fa[x] = z;
        fa[y] = x;
        fa[c[x][r]] = y;
        c[y][l] = c[x][r];
        c[x][r] = y;
        update(y);
        update(x);
    }

    void splay(int x) {
        top = 0;
        st[++top] = x;
        for (int i = x; !isroot(i); i = fa[i])
            st[++top] = fa[i];
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }

    void access(int x) {
        for (int t = 0; x > 0; t = x, x = fa[x]) {
            splay(x);
            c[x][1] = t;
            update(x);
        }
    }

    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }

    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }

    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }

    void cut(int x, int y) {
        split(x, y);
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }

    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }

    void change(int x, int w) {
        splay(x);
        v[x] = w;
    }

    void query(int x, int y) {
        split(x, y);
        output += mx[y] + "\n";
    }

    void neg(int x, int y) {
        split(x, y);
        phr(y);
    }
}
